Network-based services often require large-scale data storage. For example, Internet email services store large quantities of data in user inboxes, each user inbox itself including a sizable quantity of data. In another example, a web service may store data (e.g., images, text, etc.) to be served to client devices requesting to view a web page. This large-scale data storage is often implemented in datacenters comprised of storage devices.
Accordingly, the network-based services are configured to receive, and respond to, client requests. That is, a client device can access the network-based services to interact with data (e.g., data objects) stored in the storage devices. For instance, a client device can request to retrieve data from a storage device. Or the client device can request to have data already stored in a storage device updated (e.g., an updated document).
To handle a large number of client requests, the network-based services typically use a series of cache servers (e.g., frontend servers) configured between the client device and the storage devices. A cache server is configured to temporarily cache some of the data stored in the storage devices to improve performance of the network-based services by reducing a number of communications between the cache server and a storage device. However, many problems associated with efficiently and reliably updating the cache of a cache server can occur.